import java.util.HashMap;

public class shengXuChuXianCiShu {
    /**
     * 给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
     */
    public int binSearch(int[] data,double k) {
        int left = 0;
        int right = data.length-1;
        while(left <= right) {
            int mid = (left + right) /2;
            if (data[mid] < k) {
                left = mid + 1;
            }else if (data[mid] > k) {
                right = mid -1;
            }
        }
        return left;
    }
    public int GetNumberOfK(int[] array , int k) {
        return binSearch(array,k+0.5) - binSearch(array,k-0.5);
    }
    public int GetNumberOfK2(int [] array , int k) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < array.length;i++) {
            if (hashMap.containsKey(array[i])) {
                hashMap.put(array[i], hashMap.get(array[i]) + 1);
            }
        }
        for (int i = 0;i <array.length;i++) {
            if (hashMap.get(array[i]) == k) {
                return k;
            }
        }
        return k;
    }
}
